{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "db5c042d",
   "metadata": {},
   "source": [
    "# 习题\n",
    "## 习题21.2\n",
    "![image.png](./images/exercise2.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e42ccb2d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "R0 = [0.18104937 0.7058351  0.0649045  0.04821102]\n",
      "Rt = [0.33333333 0.22222222 0.22222222 0.22222222]\n",
      "\n",
      "R0 = [0.43176924 0.07643952 0.05834819 0.43344305]\n",
      "Rt = [0.33333333 0.22222222 0.22222222 0.22222222]\n",
      "\n",
      "R0 = [0.47205347 0.0391893  0.39826473 0.0904925 ]\n",
      "Rt = [0.33333333 0.22222222 0.22222222 0.22222222]\n",
      "\n",
      "R0 = [0.291807   0.13803864 0.35123989 0.21891446]\n",
      "Rt = [0.33333333 0.22222222 0.22222222 0.22222222]\n",
      "\n",
      "R0 = [0.47138127 0.10921891 0.04220871 0.3771911 ]\n",
      "Rt = [0.33333333 0.22222222 0.22222222 0.22222222]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "def page_rank_basic(M, R0, max_iter=1000):\n",
    "    \"\"\"\n",
    "    迭代求解基本定义的PageRank\n",
    "    :param M: 转移矩阵\n",
    "    :param R0: 初始分布向量\n",
    "    :param max_iter: 最大迭代次数\n",
    "    :return: Rt: 极限向量\n",
    "    \"\"\"\n",
    "    Rt = R0\n",
    "    for _ in range(max_iter):\n",
    "        Rt = np.dot(M, Rt)\n",
    "    return Rt\n",
    "\n",
    "# 使用例21.1的转移矩阵M\n",
    "M = np.array([[0, 1 / 2, 1, 0],\n",
    "              [1 / 3, 0, 0, 1 / 2],\n",
    "              [1 / 3, 0, 0, 1 / 2],\n",
    "              [1 / 3, 1 / 2, 0, 0]])\n",
    "\n",
    "# 使用5个不同的初始分布向量R0\n",
    "for _ in range(5):\n",
    "    R0 = np.random.rand(4)\n",
    "    R0 = R0 / np.linalg.norm(R0, ord=1)\n",
    "    Rt = page_rank_basic(M, R0)\n",
    "    print(\"R0 =\", R0)\n",
    "    print(\"Rt =\", Rt)\n",
    "    print()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4975af6e",
   "metadata": {},
   "source": [
    "# 自编程实现一般PageRank的\n",
    "scipy.sparse.csc_matrix 是 scipy 库中 sparse 模块的一个类，它代表了压缩列（Compressed Sparse Column）格式的稀疏矩阵。CSC格式是存储稀疏矩阵的一种高效方式，特别适合于列操作较多的场景，如矩阵乘法和列 slicing。\n",
    "\n",
    "在 CSC 格式中，稀疏矩阵被压缩成三个主要的数组：\n",
    "\n",
    "1. data：一个一维数组，存储了矩阵中非零元素的值。\n",
    "\n",
    "2. indices：一个一维数组，存储了非零元素的行索引。\n",
    "\n",
    "3. indptr：一个一维数组，用于指示每列的非零元素在 data 和 indices 数组中的起始位置。indptr[k] 表示第 k 列的非零元素在 data 和 indices 中的起始索引，而 indptr[k+1] 表示第 k 列的结束索引。因此，第 k 列的非零元素数量为 indptr[k+1] - indptr[k]。\n",
    "\n",
    "CSC 格式的稀疏矩阵在内存使用和计算效率方面具有以下优点：\n",
    "\n",
    "- 空间效率：由于只存储非零元素，因此对于稀疏矩阵来说，CSC 格式可以显著节省内存空间。\n",
    "- 快速列操作：CSC 格式特别适合于需要频繁访问或操作列数据的场景，因为每列的数据是连续存储的，这使得列 slicing 和矩阵乘法等操作更加高效。\n",
    "- csc_matrix 类提供了多种方法和属性，用于创建、操作和转换稀疏矩阵，包括矩阵乘法、转置、元素访问、稀疏和密集格式之间的转换等。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27e25c94",
   "metadata": {},
   "outputs": [],
   "source": [
    "#https://gist.github.com/diogojc/1338222/84d767a68da711a154778fb1d00e772d65322187\n",
    "\n",
    "import numpy as np\n",
    "from scipy.sparse import csc_matrix\n",
    "\n",
    "# 一个表示随机跳转概率的参数 s（默认为 0.85），以及一个表示收敛条件的误差阈值 maxerr（默认为 0.0001）。\n",
    "def pageRank(G, s=.85, maxerr=.0001):\n",
    "    \"\"\"\n",
    "    Computes the pagerank for each of the n states\n",
    "    Parameters\n",
    "    ----------\n",
    "    G: matrix representing state transitions\n",
    "       Gij is a binary value representing a transition from state i to j.\n",
    "    s: probability of following a transition. 1-s probability of teleporting\n",
    "       to another state.\n",
    "    maxerr: if the sum of pageranks between iterations is bellow this we will\n",
    "            have converged.\n",
    "    \"\"\"\n",
    "    n = G.shape[0]\n",
    "\n",
    "    # transform G into markov matrix A\n",
    "    A = csc_matrix(G, dtype=np.float)\n",
    "    # 计算矩阵 A 的每一行的和，即每个节点的出度。\n",
    "    rsums = np.array(A.sum(1))[:, 0]\n",
    "    # 获取矩阵 A 中非零元素的行索引和列索引。\n",
    "    ri, ci = A.nonzero\n",
    "    # 将矩阵 A 中的非零元素除以其对应的行和，即归一化出度，以创建马尔可夫矩阵。\n",
    "    A.data /= rsums[ri]\n",
    "\n",
    "    # bool array of sink states\n",
    "    sink = rsums == 0\n",
    "\n",
    "    # Compute pagerank r until we converge\n",
    "    # 初始化两个数组 ro 和 r，用于存储前一次和当前的 PageRank 值。\n",
    "    ro, r = np.zeros(n), np.ones(n)\n",
    "    while np.sum(np.abs(r - ro)) > maxerr:\n",
    "        ro = r.copy()\n",
    "        # calculate each pagerank at a time\n",
    "        for i in range(0, n):\n",
    "            # inlinks of state i\n",
    "            Ai = np.array(A[:, i].todense())[:, 0]\n",
    "            # account for sink states\n",
    "            Di = sink / float(n)\n",
    "            # account for teleportation to state i\n",
    "            Ei = np.ones(n) / float(n)\n",
    "\n",
    "            r[i] = ro.dot(Ai * s + Di * s + Ei * (1 - s))\n",
    "\n",
    "    # return normalized pagerank\n",
    "    return r / float(sum(r))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
